Матч 306, Сортирующая машина (SortMachine)

Дивизион 2, Уровень 1

Имеется машина для сортировки набора различных чисел. Она имеет только одну команду MOVE с одним аргументом. Эта команда переносит число, заданное в аргументе, в конец последовательности чисел.

Например, для сортировки массива чисел {19, 7, 8, 25} в возрастающем порядке следует совершить две команды:

1. MOVE 19, получим {7, 8, 25, 19}.

2. MOVE 25, получим {7, 8, 19, 25}.

Для заданного массива чисел необходимо найти наименьшее количество команд MOVE, в результате выполнения которых его элементы будут упорядочены по возрастанию.

Класс: SortMachine

Метод: int countMoves(vector<int> a)

Ограничения: a содержит от 1 до 50 различных чисел, -1000 £ a[i] £ 1000.

Вход. Массив чисел a.

Выход. Наименьшее количество команд MOVE, необходимых для сортировки массива а по возрастанию.

Пример входа

a

{19,7,8,25}

{1,2,3,4,5}

{1,3,4,5,6,7,8,9,2}

Пример выхода

2

0

7

РЕШЕНИЕ

сортировка

Элементы отсортированного массива можно разбить на две группы. В первую группу отнесем те числа, которые не передвигались (они стоят в массиве слева), а во вторую – которые передвигались командой MOVE. Очевидно, что дважды выполнять команду MOVE с одним и тем же числом нет смысла.

Отсортируем набор входных чисел. Двигаемся слева направо по входному и отсортированному массиву при помощи указателей i и j. Если текущие элементы массивов равны (a[i] = b[j]), то этот элемент не должен передвигаться. Иначе элемент неотсортированного массива a[i] должен переноситься в конец командой MOVE.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class SortMachine

{

public:

int countMoves(vector<int> a)

{

int i, j, res;

vector<int> b = a;

sort(b.begin(),b.end());

for(res = i = j = 0; i < a.size(); i++)

if (a[i] == b[j]) j++; else res++;

return res;

}

};